﻿#define _CRT_SECURE_NO_WARNINGS 1


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // 1. 按照左端点排序
        sort(points.begin(), points.end());
        // 2. 求互相重叠区间的数量
        int right = points[0][1];
        int ret = 1;
        for (int i = 1; i < points.size(); i++) {
            int a = points[i][0], b = points[i][1];
            if (a <= right) // 有重叠部分
            {
                right = min(right, b);
            }
            else // ⽆重叠部分
            {
                ret++;
                right = b;
            }
        }
        return ret;
    }
};

int main()
{
    vector<vector<int>> points = { {10, 16} ,{2, 8},{1, 6},{7, 12} };

    cout << Solution().findMinArrowShots(points) << endl;

    return 0;
}


